package leetcode;

/**
 * Created by baoyunfeng on 2019/8/6.
 * <p>
 * 思路1：递归，对已知解给出答案，对未知解进行递归，回归到已知问题解决。判断过多。。。记不住。GG
 * 思路2：
 */
public class Regular_Expression_Matching {

    public static void main(String args[]) {
        isMatch("abbbbbcdef", "ab*cdef");
    }

    /**
     * 这道求正则表达式匹配的题和那道 Wildcard Matching 的题很类似，不同点在于*的意义不同，在之前那道题中，*表示可以代替任意个数的字符，而这道题中的*表示之前那个字符可以有0个，1
     * 个或是多个，就是说，字符串a*b，可以表示b或是aaab，即a的个数任意，这道题的难度要相对之前那一道大一些，分的情况的要复杂一些，需要用递归Recursion来解，大概思路如下：
     * <p>
     * - 若p为空，若s也为空，返回true，反之返回false。
     * <p>
     * - 若p的长度为1，若s长度也为1，且相同或是p为'.'则返回true，反之返回false。
     * <p>
     * - 若p的第二个字符不为*，若此时s为空返回false，否则判断首字符是否匹配，且从各自的第二个字符开始调用递归函数匹配。
     * <p>
     * - 若p的第二个字符为*，进行下列循环，条件是若s不为空且首字符匹配（包括p[0]为点），调用递归函数匹配s和去掉前两个字符的p（这样做的原因是假设此时的星号的作用是让前面的字符出现0
     * 次，验证是否匹配），若匹配返回true，否则s去掉首字母（因为此时首字母匹配了，我们可以去掉s的首字母，而p由于星号的作用，可以有任意个首字母，所以不需要去掉），继续进行循环。
     * <p>
     * - 返回调用递归函数匹配s和去掉前两个字符的p的结果（这么做的原因是处理星号无法匹配的内容，比如s="ab",
     * p="a*b"，直接进入while循环后，我们发现"ab"和"b"不匹配，所以s变成"b"，那么此时跳出循环后，就到最后的return来比较"b"和"b"了，返回true。再举个例子，比如s="",
     * p="a*"，由于s为空，不会进入任何的if和while，只能到最后的return来比较了，返回true，正确）。
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch1(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        if (p.length() == 1) {
            return (s.length() == 1 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
        }
        if (p.charAt(1) != '*') {
            if (s.isEmpty()) {
                return false;
            }
            return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch1(s.substring(1), p.substring(1));
        }
        while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
            if (isMatch1(s, p.substring(2))) {
                return true;
            }
            s = s.substring(1);
        }
        return isMatch1(s, p.substring(2));
    }

//    bool isMatch(string s, string p) {
//        int m = s.size(), n = p.size();
//        vector<vector<bool>> dp (m + 1, vector < bool > (n + 1, false));
//        dp[0][0] = true;
//        for (int i = 0; i <= m; ++i) {
//            for (int j = 1; j <= n; ++j) {
//                if (j > 1 && p[j - 1] == '*') {
//                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
//                } else {
//                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
//                }
//            }
//        }
//        return dp[m][n];
//    }

    /**
     * 动归才是王道
     * <p>
     * 我们也可以用DP来解，定义一个二维的DP数组，其中dp[i][j]表示s[0,i)和p[0,j)是否match，然后有下面三种情况(下面部分摘自这个帖子)：
     * <p>
     * 1.  P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
     * 2.  P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
     * 3.  P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern
     * repeats for at least 1 times.
     *
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean dp[][] = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int realX = i - 1;
                int realY = j - 1;
                if (p.charAt(realY) == '*') {
                    boolean first = dp[i][j - 2];
                    boolean second =  j > 1 && dp[i - 1][j] && (s.charAt(realX) == p.charAt
                            (realY - 1) || p.charAt(realY - 1) == '.');
                    dp[i][j] = first|| second;


                    if(dp[i][j - 2]){
                        System.out.println("*** i:"+i+" j:"+j+"  dp:"+dp[i][j]  +  " "+first+second);
                    }else{
                        System.out.println("*@* i:"+i+" j:"+j+"  dp:"+dp[i][j] +  " "+first+second);
                    }
                } else {
                    dp[i][j] =  dp[i - 1][j - 1] && (s.charAt(realX) == p.charAt(realY) || p.charAt(realY) ==
                            '.');
                    System.out.println("### i:"+i+" j:"+j+"  dp:"+dp[i][j]);
                }
            }
            s(dp);
        }
        return dp[m][n];
    }

    private static void s(boolean dp[][]) {
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}
